package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.*;

/**
 * @author zhangjy
 * @description 二叉树的右视图
 * <p>
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * @date 2025/3/31 21:46
 */
public class RightSideView_199 {

    public static void main(String[] args) {
        // TODO 领会DFS递归、迭代
    }

    /**
     * 官解-DFS迭代
     */
    public List<Integer> rightSideView4(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Deque<TreeNode> nodeStack = new LinkedList<TreeNode>();
        Deque<Integer> depthStack = new LinkedList<Integer>();
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();

            if (node != null) {
                // 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 如果不存在对应深度的节点我们才插入
                if (!rightmostValueAtDepth.containsKey(depth)) {
                    rightmostValueAtDepth.put(depth, node.val);
                }

                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        // 记录每层最右边节点val
        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }

    /**
     * 个解-DFS（自上而下）
     */
    public List<Integer> rightSideView2(TreeNode root) {
        // 错误

        // 1.返回值、入参；
        // 返：void；入参：root
        // 2.递归终止条件
        // node == null return：
        // 3.单层逻辑
        // 右子树不空，则记录该节点val，并向下递归；反之，才记录左子树val，向下递归左子树

        List<Integer> res = new ArrayList<>();
        dfs2(root, res);
        return res;
    }

    public void dfs2(TreeNode node, List<Integer> res) {
        if (node == null) return;

        res.add(node.val);
        if (node.right != null) {
            dfs2(node.right, res);
        } else {
            dfs2(node.left, res);
        }
    }

    /**
     * 其它题解-DFS递归
     */
    public List<Integer> rightSideView3(TreeNode root) {
        // 1.返回值、入参；
        // 返：void；入参：root
        // 2.递归终止条件
        // node == null return：
        // 3.单层逻辑
        //

        List<Integer> res = new ArrayList<>();
        dfs3(root, 0, res);
        return res;
    }

    public void dfs3(TreeNode node, int depth, List<Integer> res) {
        if (node == null) return;

        // 该深度首次遇到时才记录（下面先递归右子树，后左子树保证一个深度首次记录的val必是最右边节点）
        if (depth == res.size()) {
            res.add(node.val);
        }

        // 先递归右子树，从而保证上面首次遇到的一定是最右边节点
        dfs3(node.right, depth + 1, res);
        dfs3(node.left, depth + 1, res);
    }

    /**
     * 个解-BFS（自上而下）
     * <p>
     * 分析：
     * <p>
     * 1.由示例可知，右视图相当于把每层 最右边 的节点val记录下来；
     * 2.如果要自底向上去记录每层最右边节点，首先找到叶子节点后，无法知道其父亲节点；另外，也不知道该叶子节点是否为本层最后边的节点；
     * 3.要遍历本层节点，想到层序遍历的BFS；
     * 4.BFS是记录每层所有节点，这里要找每层最右边的节点，那只需要记录每层的最后一个节点即可，因为BFS是自上而下、从左到右。
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int curLevelSize = 0;
        while (!queue.isEmpty()) {
            curLevelSize = queue.size();
            // 遍历处理本层所有节点
            for (int i = 0; i < curLevelSize; i++) {
                TreeNode poll = queue.poll();
                // 记录本层最后一个节点的val
                if (i == curLevelSize - 1) {
                    res.add(poll.val);
                }
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
        }
        return res;
    }

}
